The present invention is directed to a system for coding image information or the like.
A coding system for a Markov information source is known as a number line representation coding system for coding the information source by mapping a symbol sequence on a number line from 0.0 to 1.0 and using the binary-represented coordinates as code words.
FIG. 1 is a chart showing a concept of the system described above. For simplicity, a binary information source is employed. There is shown a memoryless source wherein r is the probability of occurrence of a symbol "1", and 1-r is the probability of occurrence of a symbol "0". If a length of output sequence of the memoryless source is set to 3, respective coordinates of C(000)--C(111) at the right end are binary-represented. The binary representation is stopped up to distinguishable digits to provide code words. With this arrangement, decoding is attainable on the receiving side by passing through the same processes as those on the transmitting side.
In such a sequence, a mapping range Ai on the number line of the symbol sequence at i-th point and minimum coordinates C.sub.i are expressed as:
when the output symbol a.sub.i is 0, EQU A.sub.i =(1-r)A.sub.i-1 EQU C.sub.i =C.sub.i-1 +rA.sub.i-1
and when the output symbol a.sub.i is 1, EQU A.sub.i =rA.sub.i-1 EQU C.sub.i =C.sub.i-1
Now, as stated in "An Overview of the Basic Principles of the Q-Coder-Adaptive Binary Arithmetic Coder" (IBM Journal of Research & Development Vol. 32, No. 6, November 1988), rA.sub.i-1 is not necessarily calculated to reduce the number of arithmetic operations such as multiplications. Instead, there is adopted a system for selecting a certain value corresponding to a Markov status from a table containing a plurality of fixed values.
Hence, when the symbols are sequentially repeated, the range A.sub.i-1 is gradually narrowed. To keep an arithmetic accuracy, normalization (A.sub.i-1 is multiplied to a power of 2) is required. According to this normalization, as a matter of course, the fixed values perpetually remain as they are in the code words. Processing is effected by executing a shift of a binary number, i.e., 1/(power of 2) during the arithmetic operation.
If rA.sub.i-1 is herein replaced with S, the above-described formulae are expressed as:
when a.sub.i is 0, EQU A.sub.i =A.sub.i-1 -S EQU C.sub.i =C.sub.i-1 +S
when a.sub.i is 1, EQU A.sub.i =S EQU C.sub.i =C.sub.i-1
The symbol range A.sub.i-1 is gradually narrowed with an increment in symbols. It is therefore required that S be gradually decreased as the symbols increase. S can be decreased concretely by performing the shift of 1/(power of 2). Alternatively, the range A.sub.i-1 is multiplied to the power of 2 on the number line, and it can be considered to employ the constant value S. This is referred to as normalization.
Note that if the symbol a.sub.i is 0, this is called MPS (More Probability Symbol: symbol having a higher probability of occurrence). Whereas if a.sub.i is 1, this is called LPS (Less Probability Symbol: symbol having a lower probability of occurrence). The MPS implies that the probability of occurrence is presumably high while a predict converting process is effected beforehand. The LPS implies that the probability is presumably low.
When the symbol a.sub.i is "1", the range A.sub.i, which is expressed as A.sub.i =rA.sub.i-1 =S, is conceived as a range of the LPS.
FIG. 2 is a block diagram depicting a conventional coding system. Referring to FIG. 2, the numeral 1 designates a register for temporarily storing values of a range allocated to the previous symbol; 2 a subtracter; 3 a changeover unit for changing over the range; 5 a changeover unit for changing over the coordinates; 6 a shifter for determining a shift quantity in the normalization; and 7 an arithmetic unit for computing a coding output.
Next, the operation will be described with reference to the drawings.
Outputted from an unillustrated prediction estimating unit to the subtracter 2 is S (a Less Probability Symbol range) selected from the table containing the plurality of values on the basis of a status of the Markov information source. The subtracter 2 obtains a difference A.sub.i-1 -S between the range S and the previous symbol range A.sub.i-1 stored in the register 1. The subtracter 2 then outputs this difference. Inputted to the changeover unit 3 are the range A.sub.i-1 -S allocated to the MPS and the range S allocated to the LPS. The changeover unit 3 changes over a range A.sub.i allocated to the symbol, depending on whether the symbol comes under the MPS or the LPS. More specifically, if the symbol is defined as the MPS, the changeover unit 3 gives forth an output as a range=A.sub.i-1 -S which is allocated to the symbol. Whereas if the symbol is the LPS, the changeover unit 3 gives forth the output as a range A.sub.i =S which is allocated to the symbol.
Depending on whether the symbol comes under the MPS or the LPS, a changeover unit 5 outputs either the LPS symbol range S or a fixed value "0" as differential coordinates .DELTA.C with respect to the minimum coordinates C.sub.i-1 of the range A.sub.i-1 allocated to the previous symbol. Namely, the changeover unit 5 gives an output as differential coordinates .DELTA.C=S, if the symbol is the MPS. If the symbol is the LPS, the unit 5 gives the output as differential coordinates .DELTA.C=0.
An output A.sub.i of the changeover unit 3 is sent to the register 1, the shifter 6 and the arithmetic unit 7.
A range A.sub.i allocated to a symbol a.sub.i is stored in the register 1. The range A.sub.i becomes data for calculating the next symbol range. The shifter 6 compares the range A.sub.i to be inputted with 1/2. If smaller than 1/2, the range A.sub.i is doubled. Thereafter, the doubled value is compared with 1/2 once again. The comparison is repeated till the range A.sub.i exceeds 1/2. A power number l when the range A.sub.i exceeds 1/2 is obtained. The power number l is outputted as a shift quantity l of the coordinates to the arithmetic unit 7. On receiving the outputs of the arithmetic unit 7, the change-over units 3 and 5 and the shifter 6, the arithmetic unit 7 computes and outputs the code words. The differential coordinates, which have cumulatively been added from the past, are stored in the arithmetic unit 7. The values cumulatively added by the arithmetic unit 7 are equal to the minimum coordinates C.sub.i-1 of the range allocated to the previous symbol. The arithmetic unit 7 adds the input differential coordinates .DELTA.C to the minimum coordinates C.sub.i-1 of the previous symbol, thereby obtaining the minimum coordinates C.sub.i of a range allocated to the present symbol. Subsequently, the arithmetic unit 7 examines whether or not there exists a coincident portion between a portion shifted by a shift quantity l (bits) of the minimum coordinates C.sub.i and a portion resultantly obtained by adding the range A.sub.i to the minimum coordinates C. If the coincident portion exists, this portion is outputted as definitely determined coordinate bits, i.e., code words.
As discussed above, when using a constant value as S, particularly the LPS range S is large. This presents a problem if the previous symbol range A.sub.i-1 which has been normalization-represented is relatively small.
This will be exemplified as follows. Now supposing that the range A.sub.i-1 allocated to the previous symbol a.sub.i-1 slightly exceeds 0.5, the symbol range A.sub.i when the symbol a.sub.i is the MPS becomes rather small. Sometimes, this symbol range A.sub.i is far smaller than A.sub.i when the symbol a.sub.i is the LPS. Namely, instead of the fact that the probability of occurrence in the MPS is originally higher than in the LPS, it follows that the range allocated to the MPS becomes smaller than the range allocated to the LPS. This leads to a decline of coding efficiency due to longer average code words. Provided that the range allocated to the MPS is invariably larger than the range allocated to the LPS, S is required to be smaller than 0.25. This is because A.sub.i-1 &gt;0.5.
Hence, when the previous symbol range A.sub.i-1 is 1.0, r=0.25. When the previous symbol range A.sub.i-1 is approximate to 0.5, r=0.5. For this reason, the probability of occurrence eventually fluctuates between 1/4 and 1/2 in terms of coding.
If this fluctuation width is reduced, the range allocation proportional to the probability of occurrence can be made. Therefore, an improvement of the coding efficiency can be expected.